#define _CRT_SECURE_NO_WARNINGS 1
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {

    int lenA = 1;
    int lenB = 1;

    struct ListNode* curA = headA;
    while (curA->next)
    {
        lenA++;
        curA = curA->next;
    }

    struct ListNode* curB = headB;
    while (curB->next)
    {
        lenB++;
        curB = curB->next;
    }

    if (curA != curB)
        return NULL;

    struct ListNode* fast = headA;
    struct ListNode* slow = headB;
    if (lenA < lenB)
    {
        fast = headB;
        slow = headA;
    }

    int k = abs(lenA - lenB);
    while (k--)
    {
        fast = fast->next;
    }

    while (fast != slow)
    {
        if (fast == slow)
            return fast;

        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

struct ListNode* detectCycle(struct ListNode* head) {

    struct ListNode* slow = head;
    struct ListNode* fast = head;

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            fast = fast->next;
            slow->next = NULL;
            return getIntersectionNode(head, fast);
        }
    }

    return NULL;
}